export class Graph {
    constructor(edges) {
        this.nodes = new Map();
        this.edges = new Map();

        edges.forEach(edge => {
            const { from, to, cost, time, departureTime } = edge;

            // 初始化节点
            if (!this.nodes.has(from)) {
                this.nodes.set(from, {
                    id: from,
                    neighbors: new Map()
                });
            }
            if (!this.nodes.has(to)) {
                this.nodes.set(to, {
                    id: to,
                    neighbors: new Map()
                });
            }

            // 初始化边，根据策略存储权重
            const nodeFrom = this.nodes.get(from);
            if (!nodeFrom.neighbors.has(to)) {
                nodeFrom.neighbors.set(to, {
                    cost: cost,
                    time: time,
                    departureTime: departureTime,
                    transfers: 1 // 默认中转次数为1，因为直接相连
                });
            } else {
                // 如果已经存在边（理论上不应该，除非数据有误），则更新中转次数（这里不考虑更新成本和时间，因为直接相连应只有一个值）
                const existingEdge = nodeFrom.neighbors.get(to);
                existingEdge.transfers = 1; // 重置为1，因为直接相连不考虑中转次数累加（或者根据实际需求调整）
            }
        });

        // 构建中转关系（用于计算中转次数）
        this.buildTransferEdges();
    }

    // 构建中转关系，用于计算中转次数
    buildTransferEdges() {
        this.nodes.forEach(node => {
            node.neighbors.forEach((neighbor, neighborId) => {
                this.edges.set(`${node.id}-${neighborId}`, neighbor);
            });
        });
    }

    // 辅助函数，将时间字符串（格式如"08:00"）转换为分钟数，方便时间计算
    timeStringToMinutes(timeStr) {
        const [hours, minutes] = timeStr.split(':').map(Number);
        return hours * 60 + minutes;
    }

    // Dijkstra算法实现，加入时间考虑
dijkstra(origin, destination, strategy = 'cost') {
    const pq = [[0, 0, origin]]; // 优先队列，初始化为起点到自身的距离为0，时间为0
    const distances = new Map();
    const arrivalTimes = new Map(); // 新增到达时间映射
    const previousNodes = new Map();
    const visited = new Set();
 
    distances.set(origin, 0);
    arrivalTimes.set(origin, 0); // 假设起点时间为0或某个固定时间
 
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]); // 按照距离升序排序
        const [currentDistance, currentTime, currentNode] = pq.shift();
 
        if (visited.has(currentNode)) continue;
        visited.add(currentNode);
 
        if (currentNode === destination) break;
 
        const node = this.nodes.get(currentNode);
        if (node) {
            node.neighbors.forEach((neighbor, neighborId) => {
                // 计算新的到达时间
                const newArrivalTime = this.timeStringToMinutes(neighbor.departureTime) + (strategy === 'time' ? neighbor.time : 0);
                // 检查时间约束：到达上一个节点的时间必须早于或等于当前边的出发时间
                const isValidTransfer = arrivalTimes.get(currentNode) <= this.timeStringToMinutes(neighbor.departureTime);
 
                // 计算新的距离（根据不同策略：成本、时间、中转次数）
                const newDistance = currentDistance + (strategy === 'cost' ? neighbor.cost : strategy === 'time' ? neighbor.time : neighbor.transfers);
 
                if (!distances.has(neighborId) || (distances.has(neighborId) && newDistance < distances.get(neighborId) && isValidTransfer)) {
                    distances.set(neighborId, newDistance);
                    arrivalTimes.set(neighborId, newArrivalTime); // 更新到达时间
                    previousNodes.set(neighborId, currentNode);
                    pq.push([newDistance, newArrivalTime, neighborId]);
                }
            });
        }
    }

        if (!distances.has(destination)) return null; // 如果没有找到路径，返回null

        // 构建路径
        const path = [];
        let currentNode = destination;
        while (currentNode!== origin) {
            path.unshift(currentNode);
            currentNode = previousNodes.get(currentNode);
        }
        path.unshift(origin); // 添加起点到路径开头

        // 构建路径边
        const pathEdges = [];
        for (let i = 0; i < path.length - 1; i++) {
            const from = path[i];
            const to = path[i + 1];
            const edge = this.edges.get(`${from}-${to}`);
            pathEdges.push({ from, to,...edge });
        }

        return {
            path: path,
            pathEdges: pathEdges,
            distance: distances.get(destination)
        };
    }
}

export default Graph;